package leetcode53;


/**
 * @Author tyy
 * @Description 53. 最大子序和
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 示例 1：
 *
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
 * @Since 2021/10/10
 */
public class Solution {

    public static void main(String[] args) {
        int[] nums = {1,-3,-5,6,-2,4};
        int i = new Solution().maxSubArray(nums);
        System.out.println("i = " + i);
    }
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = 0;// 1 -2 -5 6 4 8
        for (int num : nums) {
            if (sum > 0)
                sum += num;
            else
                sum = num;
            res = Math.max(res, sum);// 1 1 1 6 6 8
        }
        return res;
    }


}
